查询优化（Query Optimization）
由 Joe Hellerstein 介绍
被选中的读物
Ron Avnur and Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. SIGMOD, 2000.
查询的优化，是数据库技术中一个标志性的组成部分 --- 它是连接声明式语言与高效率执行之间的桥梁。查询的优化同时有着数据库实现中最难的一个部分的声誉，所以对于不同的成熟商业数据库间的清晰差异，没有必要大惊小怪。而最好的开源关系型数据库优化器，经由比较而受到限制，同时他们当中有一些相关的原生优化，可能只对于那些最为简单的查询，能够起作用。
一件非常重要的事情在于，记住不存在一款真正可以构建出“最好的”执行计划的查询优化器。首先，所有的查询优化器，都使用着估计的方法，来推测真实的查询计划开销，同时广为人知的事情在于，这些估算都可能存在膨胀的问题 --- 在某些环境下面，它们就像最坏情况，所估计的那样[^88]。第二，优化器使用启发式方法，来限制它们所选择的执行计划的搜索空间，因为这个问题是一个NP-hard问题[^86]。而就在最近，传统的两表连接操作符受到了业界的极大关注；因为在某些特定的用例下面，它们被证明不如新的多路连接算法[^121]。
除了这些注意事项之外，关系型的查询优化已经被证明相当成功，并且使得关系型数据库在实践中，取得了许多良好的用例。数据库的供应商们，花费了数年的时间，来使得它们的优化器在许多广泛的用例下面，表现地十分可靠。用户们则被教会如何同join数量的有关限制相处。优化器依旧，同时也是最大的一个部分，在于使得声明式的 SQL 查询，在大多数场景下面，比那些命令式的代码要工作地好。
而除了难以构建与调试之外，严肃的查询优化者同样有着，伴随着时间的演进而变得越来越复杂的趋势，它们已经逐渐进化地能够处理更为丰富的工作负载以及更多的边缘条件。而数据库查询优化的各种研究文献，本身也就构建出来了一个充满各种技术细节的领域 --- 它们当中的许多都已经在文献中，由研究者与IBM与微软的那些与产品密切接触的研究小组的工作人员们，进行了相关的讨论。而在这本书之中，我们仅仅将目光，聚焦于大的图景之上：查询优化的主要的架构是如何被关注到的，以及它们将在未来如何演进。
Volcano 与 Cascades 模型
让我们从当下最为前沿的技术展开讨论。对于早些时期的数据库研究而言，存在着两种可供参考的架构，其影响覆盖到了当前已经实现出来的绝大多数严肃的优化器时上。第一个就是 Selinger 等 System R 的优化器研究人员们于第三章中谈到的优化器，这是一本相当权威的教材，在许多的商用系统当中，得以实现；而每一个数据库的研究人员们，都期待理解其内部的细节。而第二个，就是由 Goetz Graefe 以及他的合作者们，经过一系列研究项目的提炼，所得出来的模型：Exodus，Volcano 以及 Cascades。Graefe 的工作，尽管并没能向 System R 的工作那样，在研究的领域同教科书中，被广泛提及，但是它依旧，在实践当中得以应用起来，尤其是在微软的 SQL Server ，以及传闻中的许多商业系统里面。Graefe 的围绕这一领域的论文，颇有内部人士的味道 --- 它的目标用户就是那些关心查询优化器实现细节的人。而在这本书里面，我们选择了 Volcano 这篇论文，作为查询优化工作，主要的代表性文章，同时我们推荐那些狂热的爱好者们，同样去读一读 Cascade 的论文[^65] --- 不仅仅是因为它的上升趋势，同样也在于它对于诸多 Volcano 模型中内部缺陷的提及，同样也在于它是本领域最新的（也是标准的）参考文献。而到了最经，两款开源的 Cascades 风格的优化器做了合并，Greenplum 的 Orca 优化器，如今成为了 Greenplum 开源组件的一个部分，同时 Apache 的 Calcite 如今同样可以为许许多多的后端查询优化器与语言所使用，包括 LINQ。
Graefe 的优化器架构非常值得关注的原因主要在于两点。首先，它被明确设计为极具拓展性。Volcano 的前瞻视野，着实值得称赞 --- 早在 MapReduce 与 大数据技术栈之前 --- 它就在探索让数据流在广泛的数据密集型应用程序中变得可用的方法。作为结果，Graefe 的优化器模型，其不仅仅可以将 SQL 编译为了一组数据流的遍历器。它们同时可以被转变为其它输入语言和执行目标的参数。在最近数年之中，伴随着专用数据模型与编程语言（参考第二章与第九章），与专用执行引擎（参考第五章）的兴起，它也成为一个高度相关的主题。而这些优化器当中的第二个创新点在于，自上向下与目标导向的搜索策略在可能的执行计划空间中，查找最便宜执行计划的应用。这个设计选择在 Graefe 的设计中，与可拓展的 API 紧密相关，但是这件事情还不是内在就有的：Starburst 系统被展示为，如何在 Selinger 的自下而上的算法中实现灵活性[^103]。对于“上推”与“下推”在查询优化中的争辩于双方阵营中，都有着各自的拥护者，且至今没有明确的赢家。与上推和下推的争辩类似的场景，也或多或少地出现在递归查询的处理文献里面[^128]。数据库优化领域的爱好者们，将会被递归查询处理以及查询优化搜索这两个方面的文献所吸引到 --- 它们直接在 Evita Raced 的优化器中得以结合，这个优化器直接依托递归查询作为实现优化器的语言，进而同时实现了上推算法和下推算法。
自适应查询处理
在1990年代之后， 一些技术的趋势表明，我们需要对于查询的优化，做出重新的思考。这些趋势包括：
- 架构于流数据上面的持续不断的查询
- 类似于在线聚合这样的交互式数据探索办法
- 对于数据库外部的数据源的查询，且这些数据源不能够提供出可信的查询数据或者性能来
- 不可预测与动态的执行环境，包括弹性与多租户配置以及类似于传感器网络这样的广泛应用的分布式系统
- 查询当中的不透明数据以及用户自定义函数，它们的数据只能够通过观察它们的行为而得出来
Eddies
在 Eddies 上面的工作，反映在由我们所选择出来的第二篇文章里面，它大力推进了适应能力的问题：如果查询在执行的途中，发生了“重新规划”（re-planning）的情况，那么我们为什么不从架构上面，移除规划与执行这两个主体？在 Eddies 的路径上面，优化器被封装为一个数据流操作器，该数据流沿着其它数据流的边缘而进行插入。它对于它们的行为有着即时的把握，而无论它们想着记录怎样的历史。而伴随着信息的不断流动，它可以经由数据流的例程来对于查询规划的剩余部分来进行控制：这些可交换的操作符的顺序由元组通过运算符路由的顺序来决定（这可是我们在这里收录的第一篇 Eddies 文章的要点），物理运算符的选择（例如 Join 算法，索引的选择）则由在数据流中多个可选的，潜在冗余的物理运算符之间的路由元组决定[^129], [^51]，而运算符的调度，则由缓冲的输入和决定下一个输出来做决定[^131]。作为一个拓展，多路查询可以通过它们的数据流，以及可供分享的通用性操作符来进行调度[^109]。Eddies在查询运算符运行时，拦截其正在进行的数据流，将数据从其输入管道传输到其输出。在这个原因之下，Eddy 的例程可以被高效地实现出来；Deshpande 则沿着这些路线而对其实现进行了增强[^50]。这种流水线路径的优势在于，Eddies 可以在执行，诸如连接之类的流水线运算符的过程之中，自适应地改变其策略，对于一则需要长期生存的查询操作符，或者一则在其完成之前，就需要将其放弃的糟糕的决策而言意义重大。而一件有趣的事情在于，最初的 Ingres 查询优化器能够在每一个元组的基础上面包含某些特定的查询优化建议[^161]。
渐进式优化
在这个系列当中，我们所选择的第三篇文章，来自于 IBM 公司，它代表着一种更加先进的方法，它对于 System R 风格的优化器，做了一定的拓展，向其加入了可编程的特性；这种通用性的科技最初由 Kabra 与 DeWitt[^93]开创出来，且在这里变得更加完善。Eddies 聚焦于操作符外部的二度优化（此处的数据就是“在不断运动的”），这项工作聚焦于内部的操作符二度优化（当数据处于“在重置的时候”）。一些包括排序，以及大多数的 Hash-Join 操作在内的传统关系型数据库运算符，都是会被阻塞的：它们假定它们的整体的输入会在产生任何外部的输出之前。这也就提供出来了一个在输入被消耗之后，将观察到的信息同优化器的输出相互比较的机会，同时使用传统的查询优化技术对于查询计划的剩余部分进行“二次优化”的机会。这种方法的缺陷在于，当运算符消耗其输入的时候，它并不会进行二次的优化，这就使得它既不适合数据流之上的查询，而对于对称散列连接等流水线操作符，也不适合在计划的初始部分中运算符选择不当而长时间运行的关系查询 --- 比如，当数据经由数据库外部的数据源访问的时候，它们并不提供有用的数据[^116], [^157]。
一件值得关注的事情在于，这两种可适应性架构，在原则上都可以共存：一个 Eddy 仅仅只是一个数据流操作符，这就意味着一个传统的优化器既可以通过连接一组流运算符的 Eddy 来构建生成查询的计划，也可以像我们在第三篇论文中所之出来的，在 数据流中的阻塞点做重新的优化。
讨论
这些材料，将我们的讨论，聚焦于数据流的架构上面，尤其是在那些开源大数据的技术栈上。Google 的 MapReduce 将数据的自适应性的讨论，倒退了十年有余，其方法就是将阻塞运算符作为一种容错机制而进行。而在2000年代的中后期，几乎不可能就数据流的优化，展开合理的讨论，因为它们与Google/Hadoop的容错模型不相兼容。而在最后的纪念之中，关于大数据方面执行框架的讨论，则一口气打开了我们的视野，因为快速增长的数据流与查询系统之间的相似性，超过了它们之间的差异性 (Tenzing, F1, Dremel, DryadLINQ, Naiad, Spark, Impala, Tez, Drill, Flink, 诸如此类)。请注意，上面列出的自适应优化的所有激励问题在今天的大数据讨论中都是非常热门的，但没有得到很好的处理。
更为普遍的，我认为，“大数据”社区在研究的领域，以及在开源的世界之中，对于查询优化的关注，都进展缓慢，同时对于系统的领域，以及查询优化的领域，造成了损害。而一切的缘由，在于那个“手工计划”的MapReduce的编程模型，其在社区讨论的生命周期，已经超过了它本应具有的生命周期。而让 Hadoopn 以及系统研究领域的社区接受诸如 SQL，LINQ 这样的声明式语言是一种好的通用式接口，又花费了相当长的实践，即使把低层次 MapReduce 风格的数据流编程作为特殊用例下面的“快速路径”保持起来，也是如此。而更多的困惑在于，即使社区已经开始构建诸如 Hive 这样的 SQL 接口，查询优化依旧只得到了很少的讨论度与很少 的实现程度。这也许就在于，查询优化，相较于良好的查询执行器，更加难于构建。又或者，这就是商业数据库与开源数据库之间的历史质量的差距结果。MySQL 在过去的十年，是一款“数据库科学”的开源技术参考，而它的查询优化器相当天真。这也许作为一个结果，许多（或者是绝大多数？）的开源大数据研究者并不理解 --- 或者相信 --- 查询优化器技术。
在任何的用例之下，这股在大数据社区的潮流已经开始涌现。声明式的查询已经作为大数据的主流接口而回归，而基本上所有的项目，至少都在起步构建一个 1980 年代风格的查询优化器。我在这里，给出这一系列的讨论，因为我非常自信，我们可以在即将到来的新的年代之中，同样看到更多的创新性查询优化路径。
References
[1] T. Condie, D. Chu, J. M. Hellerstein, and P. Maniatis. Evita raced: metacompilation for declarative networks. Proceedings
of the VLDB Endowment, 1(1):1153–1165, 2008.
[2] A. Deshpande. An initial study of overheads of eddies. ACM SIGMOD Record, 33(1):44–49, 2004.
[3] A. Deshpande and J. M. Hellerstein. Lifting the burden of history from adaptive query processing. In VLDB, 2004.
[4] A. Deshpande, Z. Ives, and V. Raman. Adaptive query processing. Foundations and Trends in Databases, 1(1):1–140,
2007.
[5] G. Graefe. The cascades framework for query optimization. IEEE Data Eng. Bull., 18(3):19–29, 1995.
[6] T. Ibaraki and T. Kameda. On the optimal nesting order for computing n-relational joins. ACM Transactions on Database
Systems (TODS), 9(3):482–502, 1984.
[7] Y. E. Ioannidis and S. Christodoulakis. On the propagation of errors in the size of join results. In SIGMOD, 1991.
[8] N. Kabra and D. J. DeWitt. Efficient mid-query re-optimization of sub-optimal query execution plans. In SIGMOD, 1998.
[9] G. M. Lohman. Grammar-like functional rules for representing query optimization alternatives. In SIGMOD, 1988.
[10] S. Madden, M. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuous queries over streams. In
SIGMOD, 2002.
[11] J. Melton, J. E. Michels, V. Josifovski, K. Kulkarni, and P. Schwarz. Sql/med: a status report. ACM SIGMOD Record,
31(3):81–89, 2002.
[12] H. Q. Ngo, E. Porat, C. R´e, and A. Rudra. Worst-case optimal join algorithms:[extended abstract]. In Proceedings of the
31st symposium on Principles of Database Systems, pages 37–48. ACM, 2012.
[13] R. Ramakrishnan and S. Sudarshan. Top-down vs. bottom-up revisited. In Proceedings of the International Logic Pro-
gramming Symposium, pages 321–336, 1991.
[14] V. Raman, A. Deshpande, and J. M. Hellerstein. Using state modules for adaptive query processing. In ICDE. IEEE,
2003.
[15] V. Raman and J. M. Hellerstein. Partial results for online query processing. In SIGMOD, pages 275–286. ACM, 2002.
[16] T. Urhan, M. J. Franklin, and L. Amsaleg. Cost-based query scrambling for initial delays. ACM SIGMOD Record,
27(2):130–141, 1998.
[17] A. N. Wilschut and P. M. Apers. Dataflow query execution in a parallel main-memory environment. In Parallel and
Distributed Information Systems, 1991., Proceedings of the First International Conference on, pages 68–77. IEEE, 1991.
[18] E. Wong and K. Youssefi. Decompositiona strategy for query processing. ACM Transactions on Database Systems
(TODS), 1(3):223–241, 1976.